import java.util.ArrayList;  
import java.util.List;  
  
public class PrimeNumbers {  
    public static void main(String[] args) {  
        long startTime = System.currentTimeMillis();  
        final int MAX = 20000;  
        boolean[] isPrime = new boolean[MAX + 1];  
          
        // 初始化数组（0和1不是素数）  
        for (int i = 2; i <= MAX; i++) {  
            isPrime[i] = true;  
        }  
          
        // 埃拉托斯特尼筛法  
        for (int i = 2; i * i <= MAX; i++) {  
            if (isPrime[i]) {  
                for (int j = i * i; j <= MAX; j += i) {  
                    isPrime[j] = false;  
                }  
            }  
        }  
          
        // 收集素数  
        List<Integer> primes = new ArrayList<>();  
        for (int i = 2; i <= MAX; i++) {  
            if (isPrime[i]) {  
                primes.add(i);  
            }  
        }  
          
        // 按每行5个输出  
        int count = 0;  
        for (int prime : primes) {  
            System.out.print(prime + "\t");  
            count++;  
            if (count % 5 == 0) {  
                System.out.println();  
            }  
        }  
          
        long endTime = System.currentTimeMillis();  
        System.out.println("\n程序总耗时: " + (endTime - startTime) + " 毫秒");  
          
        // 分析最费时部分  
        System.out.println("\n分析：最费时的部分是筛法中的双重循环，时间复杂度为O(n log log n)。");  
        System.out.println("改进建议：使用位图(BitSet)优化内存，或采用分块筛法减少缓存缺失。");  
    }  
}